/*
* 输入一个链表的头节点，反转该链表并输出反转后链表的头节点
* 
*/

#include "common.h"


/*
*/
struct ListNode* reverseList(struct ListNode* head){
    if (head == NULL)
        return head;
    
    struct ListNode* tail = head;
    struct ListNode* tmp = NULL;
    while(tail->next){
        tmp = head;             // 保存已逆转序列的头指针
        head = tail->next;      // 未逆转序列的下一个元素作为已逆转序列的头指针
        tail->next = head->next;// 已逆转序列接上未逆转序列
        head->next = tmp;       // 头指针接上已逆转序列
    }
    return head;
}

// 更加容易理解
// struct ListNode* reverseList(struct ListNode* head) {
//     struct ListNode* prev = NULL;
//     struct ListNode* curr = head;
//     while (curr != NULL) {
//         struct ListNode* nextTemp = curr->next;
//         curr->next = prev;
//         prev = curr;
//         curr = nextTemp;
//     }
//     return prev;
// }

// struct ListNode* reverseList(struct ListNode* head){
//     //判断节点长度
//     if (head == NULL || head->next == NULL)
//          return head;
//     else {
//             struct ListNode* curr = head->next;
//             struct ListNode* tmp = NULL;
//             struct ListNode* newhead = head;
//             while(curr != NULL){
//                 //保存下一个节点
//                 tmp = curr->next;
//                 curr->next = newhead;
//                 if (newhead == head)     // 不能循环，否则必须同上使用三个指针
//                     newhead->next = NULL;
//                 newhead = curr;
//                 curr = tmp;
//             }
//             return newhead;
//     }
// }


// struct ListNode* reverseList(struct ListNode* head){
//     //判断节点长度
//     if(head == NULL || head->next == NULL)
//          return head;
//     else {
//             struct ListNode* former = NULL;
//             struct ListNode* mid = head;
//             struct ListNode* latter = NULL;
//             while(mid != NULL){
//                 //保存下一个节点
//                 latter = mid->next;
//                 //让该节点指向上一个节点
//                 mid->next = former;
//                 //上一个节点走到当前节点
//                 former = mid;
//                 //当前节点走到下一个节点
//                 mid = latter;
//             }
//         return former;
//     }
// }



// struct ListNode* reverseList(struct ListNode* head){
//     //递归版本
//     if(head == NULL || head->next == NULL){
//         return head;
//     }
//     else{
//         //保存头节点
//         struct ListNode* mid = head;
//         //保存下一个节点
//         struct ListNode* latter = mid->next;
//         //递归到最后一个几点,返回转置后链表的地址
//         head = reverseList(latter);
//         //让后面的节点指向前一个节点
//         latter->next = mid;
//         //每次递归返回都赋值为空，最后一次返回将转置后的节点的next赋值为空(必要)
//         mid->next = NULL;
//         return head;
//     }
// }
